﻿#define _CRT_SECURE_NO_WARNINGS 1

#include "priority_queue.h"
using namespace std;
//一、优先队列

//1.1priority_queue的介绍

//1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
//2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
//3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特
//定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
//4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
//代器访问，并支持以下操作：
//empty()：检测容器是否为空
//size()：返回容器中有效元素个数
//front()：返回容器中第一个元素的引用
//push_back()：在容器尾部插入元素
//pop_back()：删除容器尾部元素
//5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指
//定容器类，则使用vector
//6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数
//make_heap、push_heap和pop_heap来自动完成此操作

//1.2priority_queue的使用

//优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成
//堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：
//默认情况下priority_queue是大堆。

//函数声明                                                        接口说明
//priority_queue()/priority_queue(ﬁrst,last)            构造一个空的优先级队列
//empty()                                       检测优先级队列是否为空，是返回true，否则返回
//falsetop()                                    返回优先级队列中最大(最小元素)，即堆顶元素
//push(x)                                                  在优先级队列中插入元素x
//pop()                                          删除优先级队列中最大(最小)元素，即堆顶元素

void test_priority_queue()
{
	//默认大堆
	priority_queue<int> pq;
	pq.push(3);
	pq.push(4);
	pq.push(9);
	pq.push(1);
	pq.push(2);
	//遍历
	while (!pq.empty())
	{
		cout << pq.top() << ">";
		pq.pop();
	}
	cout << endl;
	//如果是小堆，就要进行传三个模板参数(仿函数控制实现小堆）
	priority_queue<int, vector<int>, greater<int>> pq1;
	pq1.push(90);
	pq1.push(20);
	pq1.push(520);
	pq1.push(1314);
	while (!pq1.empty())
	{
		cout << pq1.top() << "<";
		pq1.pop();
	}
	cout << endl;
}

//注意：
//1. 默认情况下，priority_queue是大堆1. 默认情况下，priority_queue是大堆
//2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载

//1.3priority_queue的应用

//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//你必须设计并实现时间复杂度为 O(n) 的算法解决此问题

//方法一：使用sort对其进行排序，然后直接访问数组下标的第k-1个（时间复杂度是O（n*logn））
class Solution1
{
public:
	int findKthLargest(vector<int>& nums, int k)
	{
		//这里是函数参数，传的是匿名对象
		sort(nums.begin(), nums.end(), greater<int>());
		return nums[k - 1];
	}
};
//方法二、使用优先级队列建大堆（时间复杂度是O（N））
class Solution2
{
public:
	int findKthLargest(vector<int>& nums, int k)
	{
		priority_queue<int> pq(nums.begin(), nums.end());
		while (--k)
		{
			pq.pop();
		}
		return pq.top();
	}
};
//方法三、用前k个数建小堆,然后再把数组的剩下的n-k个数全部依次和堆顶元素进行比较，得到最后的结果就是
class Solution3
{
public:
	int findKthLargest(vector<int>& nums, int k)
	{
		//这里的greater是类模板，要传类型
		priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
		//只要数组中的数比堆顶的元素大，就把他放进去
		for (size_t i = k; i < nums.size(); ++i)
		{
			if (nums[i] > pq.top())
			{
				pq.pop();
				pq.push(nums[i]);
			}
		}
		return pq.top();
	}
};

//1.4priority_queue的模拟实现

void test_my_priority_queue()
{
	my_priority_queue::priority_queue<int> pq1;
	pq1.push(3);
	pq1.push(4);
	pq1.push(5);
	pq1.push(6);

	while(!pq1.empty())
	{
		cout << pq1.top() << "->";
		pq1.pop();
	}
	cout << endl;

	my_priority_queue::priority_queue<int, vector<int>, greater<int>> pq2;
	pq2.push(3);
	pq2.push(4);
	pq2.push(5);
	pq2.push(6);

	while (!pq2.empty())
	{
		cout << pq2.top() << "->";
		pq2.pop();
	}
	cout << endl;
}

//二、仿函数

//2.1介绍：
//仿函数又叫函数对象，仿函数（functor）是一种特殊的对象，它的行为类似于函数。
//这是通过在类中重载operator()运算符来实现的，仿函数的主要优点是它们可以像普通函数一样被调用
//同时还可以保持状态信息，这是普通函数无法做到的。

//2.2仿函数的定义和特点

//仿函数的定义：它是一个类，这个类重载了operator()，使得这个类的对象可以像函数一样被调用
//这种对象通常用于STL算法中，作为一种灵活的函数调用机制。

//仿函数的特点包括：
//1.它不是函数，而是一个类。
//2.它通过重载operator()来模拟函数调用

//2.3仿函数的使用

void test_functor()
{
	class less
	{
	public:
		bool operator()(int x, int y)
		{
			return x < y;
		}
	};
	less functor_less;
	cout << functor_less(1, 2) << endl;
	cout << functor_less(3, 1) << endl;
}
//注意：仿函数的本质就是让类对象可以像函数一样使用
int main()
{
	test_priority_queue();
	test_my_priority_queue();
	test_functor();
	return 0;
}